// https://www.lintcode.com/problem/music-pairs/

public class Solution {
    /**
     * @param musics: the musics
     * @return: calc the number of pair of music
     */
    public long musicPairs(int[] musics) {
        // write your code here
        long ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(musics);
        int max = musics[musics.length - 1];
        for (int m : musics) {
            if (!map.containsKey(m)) {
                map.put(m, 0);
            }
            map.put(m, map.get(m) + 1);
        }
        for (int i = 0; i < musics.length; ++i) {
            int m = musics[i];
            int r = 60 * ((m / 60) + 1) - m;
            map.put(m, map.get(m) - 1);
            while (r <= max) {
                if (map.containsKey(r) && (map.get(r) > 0)) {
                    ret += map.get(r);
                    r += 60;
                } else {
                    break;
                }
            }
        }
        return ret;
    }
}